#include <stdio.h>
#include <stdlib.h>

#define POP 30	/* population size */
#define LEN 20	/* geneotype length */
#define END 3000	/* number of tournaments */
#define GIFTCARD 100	/* gitf card amount */
#define WEIGHTLIM 25 /* airline weight limit */
#define REC 0.5 /* recombination rate */
#define MUT 0.1 /* mutation rate */

/* price and weight of LEN items */
int price[]={23, 10, 12, 15, 10, 13, 23, 6, 12, 3, 7, 4, 12, 21, 3, 5, 8, 9, 25, 17};
int weight[] = {20, 10, 3, 16, 8, 6, 12, 2, 4, 2, 1, 4, 7, 6, 12, 9, 2, 5, 3, 2};

int gene[POP][LEN];
int i,j;

/* calculate the total price of nth member */
int totalprice(int n)
{
	int total = 0;
	for(i=0; i<LEN; i++)
	{
		total += gene[n][i] * price[i];
	}
	return total;
}

/* calculate the total weight of nth member */
int totalweight(int n)
{
	int total = 0;
	for(i=0; i<LEN; i++)
	{
		total += gene[n][i] * weight[i];
	}
	return total;
}

/* check if the total price exceeds the gift card amount */
int overprice(int n)
{
	if(totalprice(n) > GIFTCARD)
		return 1;
	else
		return 0;
}

/* check if the total weight exceeds the airline weight limit */
int overweight(int n)
{
	if(totalweight(n) > WEIGHTLIM)
		return 1;
	else
		return 0;
}

/* initialize the population */
void init_pop(void)
{
	int s,t;
	for(s=0; s<POP; s++)
	{
		do
		{
			for(t=0; t<LEN; t++)
			{
				if((rand()/(RAND_MAX+1.0)) < 0.5)
				{
					gene[s][t] = 0;
				}
				else
				{
					gene[s][t] = 1;
				}
			}
		} while(overprice(s) || overweight(s));
	}
}

/* display the nth member as the final winner */
void display(int n)
{
	int sumprice = 0;
	int sumweight = 0;
	int z;
	printf("You should buy the following items:\r\n");
	printf("-----------------------------------\r\n");
	for(z=0; z<LEN; z++)
	{
		if(gene[n][z])
		{
			printf("Item No.%d	price: %d	weight: %d\r\n", z+1, price[z], weight[z]);
			sumprice += price[z];
			sumweight += weight[z];
		}
	}
	printf("-----------------------------------\r\n");
	printf("Your total purchase costs %d dollars, weights %d kg.\r\n", sumprice, sumweight);
}

/* Main process */
int main(void)
{
	int a, b, winner, loser, tour, finalwinner, k;

	/* initialize the population */
	init_pop();

	/* start a tournament, with total number of END tournaments */
	for(tour = 0; tour < END; tour ++)
	{
		/* randomly choose two members */
		a = (int)(POP * (rand()/(RAND_MAX+1.0)));
		b = (int)(POP * (rand()/(RAND_MAX+1.0)));
		
		/* the member with higher price wins, the other loses */
		if (totalprice(a) > totalprice(b))
		{
			winner = a;
			loser = b;
		}
		else
		{
			winner = b;
			loser = a;
		}

		/* recombine and mutates the loser at certain probability */
		do
		{
			for(k=0; k<LEN;k++)
			{
				if((rand()/(RAND_MAX+1.0)) < REC)
					gene[loser][k] = gene[winner][k];
				if ((rand()/(RAND_MAX+1.0)) < MUT)
					gene[loser][k] = 1 - gene[loser][k];
			}
		} while (overprice(loser) || overweight(loser));
	}

	/* After the algorithm is done, calculate the final winner with highest price among all members */
	finalwinner = 0;
	for (k=1; k<POP; k++)
	{
		if(totalprice(k) > totalprice(finalwinner))
		{
			finalwinner = k;
		}
	}
  display(finalwinner);
  getchar();
  return 0;
}
